#include <iostream>
#include <fstream>
#include <vector>

#define DEBUG 0

using namespace std;

// Number
typedef enum { ONE = 0x01, TWO = 0x02, THREE = 0x04 } number;  // 1, 2, 3

// Color
typedef enum { RED = 0x01, GREEN = 0x02, PURPLE = 0x04 } color; // R, G, P

// Pattern
typedef enum { EMPTY = 0x01, STRIPE = 0x02, SOLID = 0x04 } pattern;  // E, S, O

// Shape
typedef enum { OVAL = 0x01, DIAMOND = 0x02, SQUIGGLE = 0x04 } shape; // O, D, S

typedef struct elem_t {
	shape s;
	color c;
	number n;
	pattern p;
} elem;

typedef struct constraint_t {
	unsigned char s;
	unsigned char c;
	unsigned char n;
	unsigned char p;
} constraint;

// Set of 3 elements
typedef struct st_t {
	elem *e1;
	elem *e2;
	elem *e3;
} st;

typedef string puzzle[12];
typedef vector<st *> solution;

void read_puzzle(char *file, puzzle& p)
{
	fstream fs;

	fs.open(file, fstream::in);
	for (int i = 0; i < 12; i++)
		fs >> p[i];

	fs.close();

#if DEBUG 
	for (int i = 0; i < 12; i++)
		cout << p[i] << endl;
#endif	
}

string number_to_string(number n)
{
	switch(n)
	{
		case ONE : return "1";
		case TWO : return "2";
		case THREE : return "3";
	}
}

string color_to_string(color c)
{
	switch(c)
	{
		case RED : return "R";
		case GREEN : return "G";
		case PURPLE : return "P";
	}
}

string pattern_to_string(pattern p)
{
	switch(p)
	{
		case EMPTY : return "E";
		case STRIPE : return "S";
		case SOLID : return "O";
	}
}

string shape_to_string(shape s)
{
	switch(s)
	{
		case OVAL : return "O";
		case DIAMOND : return "D";
		case SQUIGGLE : return "S";
	}
}

number to_number(char c)
{
	switch (c)
	{
		case '1' : return ONE;
		case '2' : return TWO;
		case '3' : return THREE;
	}
}

color to_color(char c)
{
	switch (c)
	{
		case 'R' : return RED;
		case 'G' : return GREEN;
		case 'P' : return PURPLE;
	}
}

pattern to_pattern(char c)
{
	switch (c)
	{
		case 'E' : return EMPTY;
		case 'S' : return STRIPE;
		case 'O' : return SOLID;
	}
}

shape to_shape(char c)
{
	switch (c)
	{
		case 'O' : return OVAL;
		case 'D' : return DIAMOND;
		case 'S' : return SQUIGGLE;
	}
}

elem *get_elem(string& se)
{
	elem *e = new elem;

	e->n = to_number(se.at(0));
	e->c = to_color(se.at(1));
	e->p = to_pattern(se.at(2));
	e->s = to_shape(se.at(3));

	return e;
}

void update_constraint(constraint& ct, elem& e1, elem& e2)
{
	unsigned char s, c, n, p;

	// Constraint: An attribute (shape, color, number, pattern) 
	// is either the same across the elements of the set or all different.

	s = e1.s ^ e2.s;
	ct.s = (s == 0)? e1.s : ~s & 0x07;

	c = e1.c ^ e2.c;
	ct.c = (c == 0)? e1.c : ~c & 0x07;

	n = e1.n ^ e2.n;
	ct.n = (n == 0)? e1.n : ~n & 0x07;

	p = e1.p ^ e2.p;
	ct.p = (p == 0)? e1.p : ~p & 0x07;
}

bool satisfies(constraint& ct, elem& e)
{
	return e.s == ct.s && e.c == ct.c && e.n == ct.n && e.p == ct.p;
}

bool equal_elem(elem *e1, elem *e2)
{
	return e1->s == e2->s &&
		e1->c == e2->c &&
		e1->n == e2->n &&
		e1->p == e2->p;
}

bool equal_sets(st *s1, st *s2)
{
	return ((equal_elem(s1->e1, s2->e1) && equal_elem(s1->e2, s2->e2) && equal_elem(s1->e3, s2->e3)) ||
			(equal_elem(s1->e1, s2->e1) && equal_elem(s1->e2, s2->e3) && equal_elem(s1->e3, s2->e2)) ||
			(equal_elem(s1->e1, s2->e2) && equal_elem(s1->e2, s2->e1) && equal_elem(s1->e3, s2->e3)) ||
			(equal_elem(s1->e1, s2->e2) && equal_elem(s1->e2, s2->e3) && equal_elem(s1->e3, s2->e1)) ||
			(equal_elem(s1->e1, s2->e3) && equal_elem(s1->e2, s2->e1) && equal_elem(s1->e3, s2->e2)) ||
			(equal_elem(s1->e1, s2->e3) && equal_elem(s1->e2, s2->e2) && equal_elem(s1->e3, s2->e1)));
}

bool unique(vector<st *>& sol, st *s)
{
	vector<st *>::iterator i;
	for (i = sol.begin(); i != sol.end(); i++)
		if (equal_sets(*i, s))
			return false;

	return true;
}

void solve_puzzle(puzzle& p, solution& sol)
{
	elem *e1, *e2, *e3;
	st *s;
	constraint c;

	for (int i = 0; i < 12; i++) {
		e1 = get_elem(p[i]);

		for (int j = 0; j < 12; j++) {
			if (j == i) continue;

			e2 = get_elem(p[j]);

			c.s = OVAL | DIAMOND | SQUIGGLE;
			c.c = RED | GREEN | PURPLE;
			c.n = ONE | TWO | THREE;
			c.p = EMPTY | STRIPE | SOLID;
			update_constraint(c, *e1, *e2);

			for (int k = 0; k < 12; k++) {
				e3 = get_elem(p[k]);

				if (satisfies(c, *e3)) {
					s = new st;
					s->e1 = e1;
					s->e2 = e2;
					s->e3 = e3;
					if (unique(sol, s))
						sol.push_back(s);
					else
						delete s;
				}
			}
		}
	}
}

void print_elem(elem *e)
{
	cout << number_to_string(e->n);
	cout << color_to_string(e->c);
	cout << pattern_to_string(e->p);
	cout << shape_to_string(e->s);
}

void print_set(st *s)
{
	print_elem(s->e1);
	cout << "    ";
	print_elem(s->e2);
	cout << "    ";
	print_elem(s->e3);	
	cout << endl;
}

void print_solution(vector<st *>& sol)
{
	vector<st *>::iterator i;
	for (i = sol.begin(); i != sol.end(); i++)
		print_set((*i));
}

int main(int argc, char *argv[])
{
	puzzle p;
	solution s;

	if (argc < 2) {
		cout << "Usage: set_solver <puzzle_file>" << endl;
		return 1;
	}

	read_puzzle(argv[1], p);
	solve_puzzle(p, s);
	print_solution(s);

	return 0;
}


